package BitSet;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-11-26
 * Time: 15:47
 */

/**
 * 位图
 */
public class MyBitSet {
    public byte[] elem;
    //记录当前位图中，存在了多少个有效的数据
    public int usedSize;
    public MyBitSet() {
        this.elem = new byte[1];
    }

    /**
     * n多少位
     * 可能会多给一个字节，但是多总比少好
     * @param n
     */
    public MyBitSet(int n) {
        this.elem = new byte[n/8+1];
    }

    /**
     * 插入一个数据
     * @param val
     */
    public void set(int val) {
        if(val<0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val/8;
        //扩容
        if(arrayIndex>elem.length-1) {
            elem = Arrays.copyOf(elem,arrayIndex+1);
        }
        int bitIndex = val%8;
        elem[arrayIndex]|=(1<<bitIndex);
        usedSize++;
    }

    /**
     * 判断当前位是不是1
     * @param val
     * @return
     */
    public boolean get(int val) {
        if(val<0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val/8;
        int bitIndex = val%8;
        if((elem[arrayIndex]&(1<<bitIndex))!=0) {
            return true;
        }
        return false;
    }

    /**
     * 将对应位置置为0
     * @param val
     */
    public void reSet(int val) {
        if(val<0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val/8;
        int bitIndex = val%8;
       if((elem[arrayIndex] ^ (1<<bitIndex))==0) {
           usedSize--;
       }
        elem[arrayIndex]&= ~(1<<bitIndex);//不能使用异或，因为要是原本那个位置就是0怎么办

    }

    /**
     * 当前位图中记录元素的个数
     * @return
     */
    public int getUsedSize() {
        return usedSize;
    }

    /**
     * 排序加去重
     */
    public void sort() {
        for(int i=0;i<elem.length;i++) {
            for(int j=0;j<8;j++) {
                if((elem[i]&(1<<j))!=0) {
                    System.out.println(i*8+j);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {1,2,3,10,4,18,13};
        MyBitSet myBitSet = new MyBitSet(18);
        for(int i=0;i< array.length;i++) {
            myBitSet.set(array[i]);
        }
        System.out.println(myBitSet.getUsedSize());
        System.out.println(myBitSet.get(10));
       myBitSet.reSet(10);
        System.out.println(myBitSet.get(10));
        myBitSet.sort();

    }
}
